#include "BST.h"
#include "stdlib.h"

Node *findMin(Node *root)
{
	// no such node
	if (root == NULL)
		return NULL;

	// base case, no node smaller
	if (root->left == NULL)
		return root;

	// if left child exist, recursive call
	else
		return findMin(root->left);
}

Node *insertNode(Node **proot, int x)
{
	// insert your code here and remove the "return 0" statement

	Node *root = *proot;

	// base case, if no node then create one
	if (root == NULL)
	{
		// create new node
		Node *newRoot = (Node *)malloc(sizeof(Node));
		newRoot->key = x;
		newRoot->left = NULL;
		newRoot->right = NULL;
		return *proot = newRoot;
	}
	// duplicated key, do nothing
	if (root->key == x)
		return NULL;

	if (root->key > x)
		return insertNode(&(root->left), x); // x is smaller than root, insert left
	else
		return insertNode(&(root->right), x); // x is bigger than root, insert right

	// return 0;
}

Node *deleteNode(Node **proot, int x)
{
	// insert your code here and remove the "return 0" statement

	Node *root = *proot;

	// if no node then return
	if (root == NULL)
		return NULL;

	// x found
	if (root->key == x)
	{
		/*no child cases*/

		// if root is leaf
		if (root->left == NULL && root->right == NULL)
			*proot = NULL;

		/*only child cases*/

		// if root has only left child
		else if (root->left != NULL && root->right == NULL)
			*proot = root->left;

		// if root has only right child
		else if (root->left == NULL && root->right != NULL)
			*proot = root->right;

		/*two child cases*/
		else
		{
			Node *minright = findMin(root->right);
			Node *dminright = deleteNode(&(root->right), minright->key);
			dminright->left = root->left;
			dminright->right = root->right;
			*proot = dminright;
		}
		return root;
	}

	// find x if not match
	else if (root->key > x)
		return deleteNode(&(root->left), x);
	else
		return deleteNode(&(root->right), x);

	// return 0;
}
Node *findNode(Node *root, int x)
{
	// insert your code here and remove the "return 0" statement

	// no such node
	if (root == NULL)
		return NULL;

	// base case, node found
	if (root->key == x)
		return root;

	// search subtree
	if (root->key > x)
		return findNode(root->left, x);
	return findNode(root->right, x);

	// return 0;
}

void destroyTree(Node **proot)
{
	// insert your code here

	Node *root = *proot;

	// no such node
	if (root == NULL)
		return;

	// if node has child
	if (root->left != NULL || root->right != NULL)
	{
		destroyTree(&(root->left));
		destroyTree(&(root->right));
	}

	// if node is a leaf
	free(root);
	*proot = NULL;
	return;
}